# 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

# candidates 中的数字可以无限制重复被选取。

# 说明：

# 所有数字（包括 target）都是正整数。
# 解集不能包含重复的组合。 
# 示例 1:

# 输入: candidates = [2,3,6,7], target = 7,
# 所求解集为:
# [
# [7],
# [2,2,3]
# ]
# 示例 2:

# 输入: candidates = [2,3,5], target = 8,
# 所求解集为:
# [
#   [2,2,2,2],
#   [2,3,3],
#   [3,5]
# ]

# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/combination-sum
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

"""
执行用时 : 148 ms , 在所有 Python3 提交中击败了 19.55% 的用户
内存消耗 : 13.4 MB , 在所有 Python3 提交中击败了 37.14% 的用户
"""
from typing import List


class Solution:
    """
    可以重复利用，但还是组合，
    这个问题代表可选范围每次都是全部数组
    """

    def __init__(self):
        self.res = []

    def backtrack(self, candidates: List[int], target: int, c: List[int]):
        s = sum(c)
        if s > target:
            return
        if s == target:
            self.res.append(c)
            return

        for index in range(len(candidates)):
            self.backtrack(candidates[index:], target, c + [candidates[index]])

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not target or not candidates:
            return []
        self.backtrack(candidates, target, [])
        return self.res


if __name__ == "__main__":
    print(Solution().combinationSum([2, 3, 6, 7], 7))
